package day014;

import java.util.Scanner;

class Object {                                                 //定义物品类，包含物品序号和单位重量价值
    int id;
    double d;
}

public class Test5_2_1 {

    static final int M = 105;
    static int i, j, n, W;                                        //n表示n个物品，W表示购物车的容量
    static int[] w = new int[M];                                 //w[i]表示第i个物品的重量
    static int[] v = new int[M];                                 //v[i]表示第i个物品的价值
    static int cw, cp, bestp;
    static int[] x = new int[M];                                 //表示第i个物品是否放入购物车
    static int[] bestx = new int[M];                             //当前最优解

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入物品的个数n：");
        n = scanner.nextInt();
        System.out.println("请输入购物车的容量W：");
        W = scanner.nextInt();
        System.out.println("请依次输入每个物品的重量w和价值v，用空格分开：");
        for (i = 1; i <= n; i++) {
            w[i] = scanner.nextInt();
            v[i] = scanner.nextInt();
        }
        knapsack(W, n);                                           //背包问题求解
        scanner.close();
    }

    public static void knapsack(int W, int n) {
        cw = 0;                                                    //初始化当前放入购物车的物品重量为0
        cp = 0;                                                    //初始化当前放入购物车的物品价值为0
        bestp = 0;                                                 //初始化当前最优值为0
        int sumw = 0;                                              //用来统计所有物品的总重量
        int sumv = 0;                                              //用来统计所有物品的总价值
        Object[] Q = new Object[n];                                //用来按单位重量价值排序
        int[] a = new int[n + 1], b = new int[n + 1];                     //辅助数组
        for (i = 1; i <= n; i++) {
            Q[i - 1] = new Object();
            Q[i - 1].id = i;
            Q[i - 1].d = v[i] / w[i];
            sumw += w[i];
            sumv += v[i];
        }
        if (sumw <= W) {                                            //所有物品可放入购物车
            bestp = sumv;
            System.out.println("放入购物车的物品最大价值为：" + bestp);
            System.out.println("所有的物品均放入购物车。");
            return;
        }

        selectionSort(Q);                                        //按单位重量价值从大到小进行排序
        for (i = 1; i <= n; i++) {
            a[i] = w[Q[i - 1].id];                                   //排序后的重量
            b[i] = v[Q[i - 1].id];                                   //排序后的价值
        }
        for (i = 1; i <= n; i++) {
            w[i] = a[i];
            v[i] = b[i];
        }

        backTrack(1);                                            //从第一层开始搜索
        System.out.println("放入购物车的物品最大价值为：" + bestp);
        System.out.print("放入购物车的物品序号为：");
        for (i = 1; i <= n; i++) {
            if (bestx[i] == 1)
                System.out.print(Q[i - 1].id + " ");
        }
        System.out.println();
    }

    /*用于搜索空间数，t表示当前扩展结点在第t层*/
    public static void backTrack(int t) {
        if (t > n) {                                                //已经到达叶子结点，记录最优值最优解
            for (j = 1; j <= n; j++) {                                  //保存最优解
                bestx[j] = x[j];
            }
            bestp = cp;
            return;                                              //保存当前最优值
        }

        if (cw + w[t] <= W) {                                         //如果满足约束条件则搜索左子树即放入物品
            x[t] = 1;                                              //放入购物车
            cw += w[t];                                            //购物车当前的重量增加
            cp += v[t];                                            //购物车当前的价值增加
            backTrack(t + 1);                                      //递推深度优先搜索第t+1层

            cw -= w[t];                                            //上向回归时要把增加的值减去
            cp -= v[t];
        }

        if (bound(t + 1) > bestp) {                                   //如果满足限界条件则搜索右子树
            x[t] = 0;                                              //不放入物品，当前放入物品重量价值均不改变
            backTrack(t + 1);                                      //深度优先搜索第t+1层
        }
    }

    /*计算上界，可容纳剩余物品的最大价值*/
    public static int bound(int i) {
        int cleft = W - cw;                                        //购物车剩余容量
        int brp = 0;
        while (i <= n && w[i] < cleft) {                              //加快剪枝速度
            cleft -= w[i];
            brp += v[i];
            i++;
        }
        if (i < n)                                                //采用切割的方式装满背包，求解时不允许切割
            brp += v[i] / w[i] * cleft;
        return cp + brp;
    }

    public static void selectionSort(Object[] array) {          //选择排序按单位重量价值从大到小排序

        Object temp = new Object();
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = i + 1; j <= array.length - 1; j++) {
                if (array[i].d < array[j].d) {
                    temp = array[i];                          //要将类的所有成员变量进行换位置，因为值是相互对应的
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
        }
    }

}